{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Smallest Number With Given Digit Product"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: smallestNumber"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #给定数字乘积的最小数字"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个 <strong>正</strong> 整数 <code>n</code>，返回一个字符串，表示 <strong>最小的正整数</strong>，使其各位数字的乘积等于 <code>n</code>&nbsp;，如果不存在这样的数字，则返回 <code>\"-1\"</code>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><b>示例 1：</b></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 105\n",
    "<b>输出：</b>\"357\"\n",
    "<b>解释：</b>3 * 5 * 7 = 105。可以证明，357 是乘积等于 105 的最小数字。因此答案为 \"105\"。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 7\n",
    "<b>输出：</b>\"7\"\n",
    "<b>解释：</b>由于 7 只有一位数字，其各位数字的乘积为 7。由于数字 1 到 6 的乘积分别为 1 到 6，所以答案为 \"7\"。可以证明 7 是乘积等于 7 的最小数字。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 44\n",
    "<b>输出：</b>\"-1\"\n",
    "<b>解释：</b>可以证明，没有数字的各位数字乘积等于 44。因此答案为 \"-1\"。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>18</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [smallest-number-with-given-digit-product](https://leetcode.cn/problems/smallest-number-with-given-digit-product/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [smallest-number-with-given-digit-product](https://leetcode.cn/problems/smallest-number-with-given-digit-product/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['105', '7', '44']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        if n < 10:\n",
    "            return str(n)\n",
    "\n",
    "        res = \"\"\n",
    "        hs = defaultdict(int)\n",
    "\n",
    "        for p in range(9, 1, -1):\n",
    "            while n != 1 and n % p == 0:\n",
    "                n //= p\n",
    "                hs[p] += 1\n",
    "\n",
    "            if n == 1:\n",
    "                for i in range(2, 10):\n",
    "                    str_i = str(i)\n",
    "                    while hs[i] != 0:\n",
    "                        res += str_i\n",
    "                        hs[i] -= 1\n",
    "                return res\n",
    "\n",
    "        return \"-1\"    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        if n < 10:\n",
    "            return str(n)\n",
    "\n",
    "        res = \"\"\n",
    "\n",
    "        for p in range(9, 1, -1):\n",
    "            str_p = str(p)\n",
    "            while n != 1 and n % p == 0:\n",
    "                n //= p\n",
    "                res = str_p + res\n",
    "\n",
    "            if n == 1:\n",
    "                return res\n",
    "\n",
    "        return \"-1\"    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        if n == 1:\n",
    "            return \"1\"\n",
    "        ans = []\n",
    "        while n != 1:\n",
    "            for num in range(9, 1, -1):\n",
    "                if n % num == 0:\n",
    "                    ans.append(num)\n",
    "                    n //= num \n",
    "                    break\n",
    "            else:\n",
    "                return \"-1\"\n",
    "        ans.sort()\n",
    "        return ''.join(map(str, ans))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        if n==1:return \"1\"\n",
    "        k=9\n",
    "        res=[]\n",
    "        while k>1:\n",
    "            while n%k==0:\n",
    "                res.append(str(k))\n",
    "                n//=k\n",
    "            k-=1\n",
    "        if n!=1:return \"-1\"\n",
    "        res.reverse()\n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        # 其实就是分解质因数，分解成个位数相乘\n",
    "        if n == 1: return \"1\"\n",
    "        lis = []\n",
    "        for i in range(9, 1, -1):\n",
    "            while n % i == 0:\n",
    "                n //= i\n",
    "                lis.append(i)\n",
    "        return \"\".join(str(i) for i in lis[::-1]) if n == 1 else \"-1\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        if n == 1:\n",
    "            return \"1\"\n",
    "        ans = []\n",
    "        while n != 1:\n",
    "            for num in range(9, 1, -1):\n",
    "                if n % num == 0:\n",
    "                    ans.append(num)\n",
    "                    n //= num \n",
    "                    break\n",
    "            else:\n",
    "                return \"-1\"\n",
    "        ans.sort()\n",
    "        return ''.join(map(str, ans))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "    如果你是一个质数，并没有1到9的\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        # if n == 1:\n",
    "        #     return '1'\n",
    "        # @cache\n",
    "        # def helper(num: int) -> str:\n",
    "        #     if num == 1:\n",
    "        #         return ''\n",
    "        #     if num < 10:\n",
    "        #         return str(num)\n",
    "        #     for i in range(2, 10):\n",
    "        #         if num % i == 0:\n",
    "        #             if helper(num // i) != '-1':\n",
    "        #                 return str(i) + helper(num // i)\n",
    "        #             else:\n",
    "        #                 return '-1'\n",
    "        #     else:\n",
    "        #         return '-1'\n",
    "        # return helper(n)\n",
    "        if n == 1:\n",
    "            return '1'\n",
    "        cnt = [0] * 10\n",
    "        for i in range(9, 1, -1):\n",
    "            while n % i == 0:\n",
    "                n //= i\n",
    "                cnt[i] += 1\n",
    "        if n > 1:\n",
    "            return '-1'\n",
    "        return ''.join(str(i) * cnt[i] for i in range(2, 10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        cnt = [0] * 10\n",
    "        for i in range(9, 1, -1):\n",
    "            while n % i == 0:\n",
    "                n //= i\n",
    "                cnt[i] += 1\n",
    "        if n > 1:\n",
    "            return '-1'\n",
    "        ans = ''.join(str(i) * cnt[i] for i in range(2, 10))\n",
    "        return ans if ans else '1'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        ans=[]\n",
    "        if n==1:\n",
    "            return \"1\"\n",
    "        for i in range(9,1,-1):\n",
    "            while n%i==0:\n",
    "                n=n//i\n",
    "                ans.append(i)\n",
    "        if n!=1:\n",
    "            return \"-1\"\n",
    "        return \"\".join(map(str,sorted(ans)))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 贪心 + 因数分解\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        if n == 1:\n",
    "            return \"1\"\n",
    "\n",
    "        lis = []\n",
    "        for i in range(9, 1, -1):\n",
    "            while n % i == 0:\n",
    "                n //= i\n",
    "                lis.append(i)\n",
    "\n",
    "        return \"\".join(str(i) for i in lis[::-1]) if n == 1 else \"-1\"\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        if n < 10:\n",
    "            return str(n)\n",
    "        cnt = Counter()\n",
    "        ans = ''\n",
    "        for i in range(9, 1, -1):\n",
    "            while n % i == 0:\n",
    "                n //= i\n",
    "                ans = str(i) + ans\n",
    "        return ans if n == 1 else '-1'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        if n == 1: return \"1\"\n",
    "        list = []\n",
    "        for i in range(9, 1, -1):\n",
    "            while n % i == 0:\n",
    "                n //= i\n",
    "                list.append(i)\n",
    "        return \"\".join(str(i) for i in list[::-1]) if n == 1 else \"-1\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        if n == 1:\n",
    "            return \"1\"\n",
    "\n",
    "        cnts = [0] * 10\n",
    "        for i in range(9,1,-1):\n",
    "            while n % i == 0:\n",
    "                n //= i \n",
    "                cnts[i]+=1\n",
    "            if n == 1:\n",
    "                break \n",
    "        else:\n",
    "            return \"-1\"\n",
    "\n",
    "        return \"\".join([str(i) * cnts[i] for i in range(2,10)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "\n",
    "        if n==1: return \"1\"\n",
    "        res = \"\"\n",
    "        for p in range(9,1,-1):\n",
    "            while n%p==0:\n",
    "                res+=str(p)\n",
    "                n//=p\n",
    "        return res[::-1] if n==1 else \"-1\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        if n == 1:\n",
    "            return '1'\n",
    "        ans = []\n",
    "        for i in range(9,1,-1):\n",
    "            if n == 1:\n",
    "                break\n",
    "            while n % i == 0:\n",
    "                n //= i\n",
    "                ans.append(str(i))\n",
    "        return ''.join(ans)[::-1] if n == 1 else '-1'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        ans = ''\n",
    "        if n == 1:\n",
    "            return '1'\n",
    "        for i in range(9, 1, -1):\n",
    "            if n == 1:\n",
    "                break\n",
    "            while n % i == 0:\n",
    "                n //= i\n",
    "                ans += str(i)\n",
    "        if ans == '':\n",
    "            return '-1'\n",
    "        return ans[::-1] if n == 1 else '-1'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        if n == 1: return \"1\"\n",
    "        lis = []\n",
    "        for i in range(9,1,-1):\n",
    "            while n % i == 0:\n",
    "                n //= i\n",
    "                lis.append(i)\n",
    "        return \"\".join(str(i) for i in lis[::-1]) if n == 1 else \"-1\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        cnt = [0] * 10\n",
    "        for i in range(9, 1, -1):\n",
    "            while n % i == 0:\n",
    "                n //= i\n",
    "                cnt[i] += 1\n",
    "        if n > 1:\n",
    "            return \"-1\"\n",
    "        ans = \"\".join(str(i) * cnt[i] for i in range(2, 10))\n",
    "        return ans if ans else \"1\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        if n == 1:\n",
    "            return \"1\"\n",
    "        ans = []\n",
    "        for i in range(9, 1, -1):\n",
    "            while n % i == 0:\n",
    "                ans.append(str(i))\n",
    "                n //= i\n",
    "        return \"-1\" if n > 10 else \"\".join(ans)[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        if n == 1:\n",
    "            return '1'\n",
    "        res = []\n",
    "        for d in range(9, 1, -1):\n",
    "            while n % d == 0:\n",
    "                n //= d\n",
    "                res.append(str(d))\n",
    "        if n > 1:\n",
    "            return '-1'\n",
    "        else:\n",
    "            return ''.join(reversed(res))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        if n == 1:\n",
    "            return \"1\"\n",
    "        counter = defaultdict(int)\n",
    "        for f in [2, 3, 5, 7]:\n",
    "            while n % f == 0:\n",
    "                n //= f\n",
    "                counter[f] += 1\n",
    "\n",
    "        if n > 1:\n",
    "            return \"-1\"\n",
    "\n",
    "        while counter[3] >= 2:\n",
    "            counter[3] -= 2\n",
    "            counter[9] += 1\n",
    "        while counter[2] >= 3:\n",
    "            counter[2] -= 3\n",
    "            counter[8] += 1\n",
    "        while counter[2] >= 1 and counter[3] >= 1:\n",
    "            counter[2] -= 1\n",
    "            counter[3] -= 1\n",
    "            counter[6] += 1\n",
    "        while counter[2] >= 2:\n",
    "            counter[2] -= 2\n",
    "            counter[4] += 1\n",
    "\n",
    "        return \"\".join(str(k) * v for k, v in sorted(counter.items()))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        if n == 1:\n",
    "            return '1'\n",
    "        ans = []\n",
    "        for i in range(9, 1, -1):\n",
    "            while n % i == 0:\n",
    "                ans.append(i)\n",
    "                n //= i\n",
    "        if n != 1:\n",
    "            return '-1'\n",
    "        ans.sort()\n",
    "        return ''.join(map(str, ans))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        cnt = [0] * 10\n",
    "        primes = [7, 5, 3, 2]\n",
    "        for p in primes:\n",
    "            while n % p == 0:\n",
    "                cnt[p] += 1\n",
    "                n //= p\n",
    "        if n > 1:\n",
    "            return '-1'\n",
    "        ans = '9' * (cnt[3] // 2) + '8' * (cnt[2] // 3) + '7' * cnt[7]\n",
    "        cnt[3] %= 2\n",
    "        cnt[2] %= 3\n",
    "        if cnt[3] and cnt[2]:\n",
    "            ans = ans + '6'\n",
    "            cnt[3] -= 1\n",
    "            cnt[2] -= 1\n",
    "        if cnt[5] > 0:\n",
    "            ans = ans + '5' * cnt[5]\n",
    "        if cnt[2] == 2:\n",
    "            ans = ans + '4'\n",
    "            cnt[2] -= 2\n",
    "        if cnt[3] == 1:\n",
    "            ans = ans + '3'\n",
    "        if cnt[2] == 1:\n",
    "            ans = ans + '2'\n",
    "        return ans[::-1] if ans else '1'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        if n == 1: return \"1\"\n",
    "        lis = []\n",
    "        for i in range(9,1,-1):\n",
    "            while n % i == 0:\n",
    "                n //= i\n",
    "                lis.append(i)\n",
    "            if n == 1: break\n",
    "        return \"\".join(str(i) for i in lis[::-1]) if n == 1 else \"-1\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        if n == 1:\n",
    "            return \"1\"\n",
    "        sb = []\n",
    "        for p in range(9, 1, -1):\n",
    "            while n % p == 0:\n",
    "                sb.append(str(p))\n",
    "                n //= p\n",
    "        if n != 1:\n",
    "            return \"-1\"\n",
    "        return \"\".join(sb[::-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        def f(x, s):\n",
    "            if x < 10:\n",
    "                return s+str(x)\n",
    "            for i in range(9, 1, -1):\n",
    "                if x % i == 0:\n",
    "                    r = f(x//i, s+str(i))\n",
    "                    if r != '-1':\n",
    "                        return r\n",
    "            return '-1'\n",
    "        s = f(n, '')  \n",
    "        if s == '-1':\n",
    "            return s\n",
    "        r = ''\n",
    "        i = len(s)-1\n",
    "        while i >= 0:\n",
    "            if i-1 >= 0:\n",
    "                if int(s[i]) * int(s[i-1]) < 10:\n",
    "                    r += str(int(s[i]) * int(s[i-1]))\n",
    "                    i -= 2\n",
    "                else:\n",
    "                    r += s[i]\n",
    "                    i -= 1\n",
    "            else:\n",
    "                r += s[i]\n",
    "                i -= 1\n",
    "        return r\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        if n < 10:\n",
    "            return str(n)\n",
    "        ans = []\n",
    "        while n > 1:\n",
    "            ok = False\n",
    "            for i in range(9, 1, -1):\n",
    "                if n % i == 0:\n",
    "                    ans.append(i)\n",
    "                    n //= i\n",
    "                    ok = True\n",
    "                    break\n",
    "            if not ok :\n",
    "                break\n",
    "        if n > 10: return \"-1\"\n",
    "        ans.sort()\n",
    "        return \"\".join(map(str, ans))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "\n",
    "        if n==1: return \"1\"\n",
    "        cnt = [0]*8\n",
    "        for p in [2,3,5,7]:\n",
    "            while n%p==0:\n",
    "                n//=p\n",
    "                cnt[p]+=1\n",
    "        if n>1: return \"-1\"\n",
    "\n",
    "        @cache\n",
    "        def insert(cur,nxt):\n",
    "            for j in range(len(cur)):\n",
    "                if cur[j]>nxt:\n",
    "                    return cur[:j]+nxt+cur[j:]\n",
    "            return cur+nxt\n",
    "\n",
    "        dp = [[\"-1\" for j in range(cnt[3]+1)] for i in range(cnt[2]+1)]\n",
    "        dp[0][0]=\"\"\n",
    "\n",
    "        for cnt2 in range(cnt[2]+1):\n",
    "            for cnt3 in range(cnt[3]+1):\n",
    "                possible = [[\"2\",1,0],[\"4\",2,0],[\"8\",3,0],[\"3\",0,1],[\"9\",0,2],[\"6\",1,1]]\n",
    "                mn = 64\n",
    "                for nxt,cnt2n,cnt3n in possible:\n",
    "                    if cnt2>=cnt2n and cnt3>=cnt3n:\n",
    "                        temp = insert(dp[cnt2-cnt2n][cnt3-cnt3n],nxt)\n",
    "                        if dp[cnt2][cnt3]==\"-1\" or len(temp)<mn or (len(temp)==mn and temp<dp[cnt2][cnt3]):\n",
    "                            mn = len(temp)\n",
    "                            dp[cnt2][cnt3]=temp\n",
    "\n",
    "        return \"\".join(sorted(\"5\"*cnt[5]+\"7\"*cnt[7]+dp[-1][-1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "from heapq import *\n",
    "from sys import *\n",
    "from math import *\n",
    "from itertools import *\n",
    "from functools import *\n",
    "from string import *\n",
    "from bisect import *\n",
    "from graphlib import *\n",
    "from sortedcontainers import *\n",
    "from copy import *\n",
    "\n",
    "@cache\n",
    "def get_prime_factors(n: int) -> list:\n",
    "    factors, i = [], 2\n",
    "    while i ** 2 <= n:\n",
    "        if i >= 10 and n >= 10: return []\n",
    "        if n % i: i += 1\n",
    "        else:\n",
    "            n //= i\n",
    "            factors.append(i)\n",
    "    if n > 1: factors.append(n)\n",
    "    return factors\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        if n == 1: return \"1\"\n",
    "        factors = get_prime_factors(n) # 包含重复元素\n",
    "        \n",
    "        if not factors: return \"-1\"\n",
    "        if max(factors) >= 10: return \"-1\"\n",
    "        cnts = Counter(factors)\n",
    "        cnts[8], cnts[2] = divmod(cnts[2], 3)\n",
    "        cnts[9], cnts[3] = divmod(cnts[3], 2)\n",
    "        if cnts[2] and cnts[3]:\n",
    "            cnts[6] += 1\n",
    "            cnts[2] -= 1\n",
    "            cnts[3] -= 1\n",
    "        if cnts[2] == 2: \n",
    "            cnts[4] += 1\n",
    "            cnts[2] = 0\n",
    "        ans = \"\"\n",
    "        for k in sorted(cnts.keys()):\n",
    "            ans += str(k) * cnts[k]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "\n",
    "        if n==1: return \"1\"\n",
    "        cnt = [0]*8\n",
    "        for p in [2,3,5,7]:\n",
    "            while n%p==0:\n",
    "                n//=p\n",
    "                cnt[p]+=1\n",
    "        if n>1: return \"-1\"\n",
    "\n",
    "        @cache\n",
    "        def dfs(cnt2,cnt3):\n",
    "            if cnt2+cnt3==0: return \"\"\n",
    "            mn = 64\n",
    "            possible = [[\"2\",1,0],[\"4\",2,0],[\"8\",3,0],[\"3\",0,1],[\"9\",0,2],[\"6\",1,1]]\n",
    "            res = \"\"\n",
    "            for nxt,cnt2n,cnt3n in possible:\n",
    "                if cnt2>=cnt2n and cnt3>=cnt3n:\n",
    "                    temp = nxt+dfs(cnt2-cnt2n,cnt3-cnt3n)\n",
    "                    if len(temp)<mn or (len(temp)==mn and \"\".join(sorted(temp))<\"\".join(sorted(res))):\n",
    "                        mn = len(temp)\n",
    "                        res = temp            \n",
    "            return res\n",
    "\n",
    "        return \"\".join(sorted(\"5\"*cnt[5]+\"7\"*cnt[7]+dfs(cnt[2],cnt[3])))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        \"\"\"\n",
    "\n",
    "        :param n:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        if n == 1:\n",
    "            return '1'\n",
    "        if n in [4,6,8,9]:\n",
    "            return str(n)\n",
    "\n",
    "        def prime_factorization(n):\n",
    "            i = 2\n",
    "            factors = []\n",
    "            while i * i <= n:\n",
    "                if n % i:\n",
    "                    i += 1\n",
    "                    if i > 9:\n",
    "                        return \"-1\"\n",
    "                else:\n",
    "                    n //= i\n",
    "                    factors.append(i)\n",
    "            if n > 1:\n",
    "                if n > 9:\n",
    "                    return \"-1\"\n",
    "                factors.append(n)\n",
    "            return factors\n",
    "\n",
    "        ll = prime_factorization(n)\n",
    "        \n",
    "        if ll == \"-1\":\n",
    "            return ll\n",
    "\n",
    "        for i in ll:\n",
    "            if i > 9:\n",
    "                return '-1'\n",
    "        m1 = defaultdict(int)\n",
    "        for i in ll:\n",
    "            m1[i] += 1\n",
    "        v3 = m1.get(3, 0)\n",
    "        gap1 = v3 // 2\n",
    "        m1[3] -= gap1 * 2\n",
    "        m1[9] += gap1\n",
    "\n",
    "        v2 = m1.get(2, 0)\n",
    "        gap2 = v2 // 3\n",
    "        m1[2] -= gap2 * 3\n",
    "        m1[8] += gap2\n",
    "\n",
    "        v2 = m1.get(2, 0)\n",
    "        v3 = m1.get(3, 0)\n",
    "        gap2 = min(v2, v3)\n",
    "        m1[2] -= gap2\n",
    "        m1[3] -= gap2\n",
    "        m1[6] += gap2\n",
    "\n",
    "        v2 = m1.get(2, 0)\n",
    "        gap2 = v2 // 2\n",
    "        m1[2] -= gap2 * 2\n",
    "        m1[4] += gap2\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        xx = []\n",
    "        for i in m1:\n",
    "            for j in range(m1[i]):\n",
    "                xx.append(i)\n",
    "        xx.sort()\n",
    "        return ''.join([str(i) for i in xx])\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
